home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / security / doc / clippings / 920115-01 < prev    next >
Encoding:
Text File  |  1992-01-26  |  2.6 KB  |  74 lines
  1. Newsgroups: sci.crypt,alt.security
  2. From: mkwan@mullauna.cs.mu.OZ.AU (Matthew Kwan)
  3. Subject: Biham & Shamir break DES
  4. Message-ID: <mkwan.695456528@mullauna.cs.mu.OZ.AU>
  5. Keywords: DES differential cryptanalysis
  6. Organization: Computer Science, University of Melbourne, Australia
  7. Date: Wed, 15 Jan 1992 06:22:08 GMT
  8.  
  9. Well, I've finally got a copy of the paper describing
  10. Biham and Shamir's new attack on DES (thanks Eli!).
  11.  
  12. A quick summary - it is a chosen-plaintext attack, requiring
  13. approximately 2^47 plaintexts (yes, the rumours were correct).
  14.  
  15. To save further explanation, I'll simply type in the first page
  16. verbatim.
  17.  
  18.  
  19.     Differential Cryptanalysis of the
  20.         Full 16-round DES
  21.  
  22.     Eli Biham
  23.     Computer Science Department
  24.     Technion - Israel Institute of Technology
  25.     Haifa 32000, Israel
  26.  
  27.     Adi Shamir
  28.     Dept of Applied Math and Comp Sci
  29.     The Weizmann Institute of Science
  30.     Rehovot 76100, Israel
  31.  
  32.     December 19, 1991
  33.  
  34.     Abstract
  35.  
  36.   In this paper we develop the first known attack which is capable of breaking
  37. the full 16 round DES in less than the 2^55 complexity of exhaustive search.
  38. The data analysis phase computes the key by analyzing about 2^36 ciphertexts
  39. in 2^37 time. The 2^36 usable ciphertexts are obtained during the data
  40. collection phase from a pool of 2^47 chosen plaintexts by a simple bit
  41. repetition criteria which discards more than 99.9% of the ciphertexts as soon
  42. as they are generated. While earlier versions of differential attacks were
  43. based on huge counter arrays, the new attack can be carried out even if the
  44. analyzed ciphertexts are derived from up to 2^33 different keys due to frequent
  45. key changes during the data collection phase. The attack can be carried out
  46. incrementally with any number of available ciphertexts, and probability of
  47. success grows linearly with this number (e.g., when 2^29 usable ciphertexts
  48. are generated from a smaller pool of 2^40 plaintexts, the analysis time
  49. decreases to 2^30 and the probability of success is about 1%).
  50.  
  51.  
  52. I haven't studied the paper carefully, but from what I've read, it appears
  53. they've managed to overcome the signal/noise problems in the old version,
  54. and make use of a 13 round characteristic (with prob 2^-47) to break the
  55. 16 round DES. The old version had to use a 15 round attack.
  56.  
  57. The paper is 10 pages long, and is available from Technion Comp Sci Dept,
  58. where it is Technical Report #708.
  59.  
  60. Please don't ask me any difficult questions about it, since I retired
  61. >From cryptography last week ;-)
  62.  
  63. mkwan
  64.  
  65. --------------------------------------------------------------------
  66. Matthew Kwan
  67.  
  68. who is no longer associated with
  69.  
  70. Centre for Computer Security Research
  71. Australian Defence Force Academy
  72. Canberra ACT 2600
  73.  
  74.